import heapq
from typing import List


class Solution:
    _MOD = 10 ** 9 + 7

    def __init__(self):
        self.left_sum, self.right_sum = 0, 0  # 中位数左侧的差值的绝对值和、中位数右侧的差值的绝对值和
        self.left, self.mid, self.right = [], None, []  # 中位数左侧的差值（堆）、中位数差值、中位数右侧的差值（堆）

    def numsGame(self, nums: List[int]) -> List[int]:
        size = len(nums)

        ans = []

        for i in range(size):
            # 计算与从1开始的等差数列的期望值的差值：实际值-期望值
            expect = i + 1
            differ = nums[i] - expect

            # 维护差值堆和差值的绝对值和
            if self.mid is None:  # 添加第奇数个的情况
                if not self.left and not self.right:  # 添加第1个数的情况
                    self.mid = differ
                else:
                    if (-self.left[0]) <= differ <= self.right[0]:  # 新添加的数正好的中位数的情况
                        self.mid = differ
                    elif differ < -self.left[0]:  # 新添加的数在中位数左侧的情况
                        old_left = self.left_pop()
                        self.left_push(differ)
                        self.mid = old_left
                    else:  # 新添加的数在中位数右侧的情况
                        old_right = self.right_pop()
                        self.right_push(differ)
                        self.mid = old_right
            else:  # 添加第偶数个的情况
                if differ >= self.mid:  # 新添加的数在中位数右侧的情况
                    self.left_push(self.mid)
                    self.right_push(differ)
                else:  # 新添加的数在中位数左侧的情况
                    self.left_push(differ)
                    self.right_push(self.mid)
                self.mid = None

            # 计算当前位结果
            if self.mid is not None:  # 当前有奇数个差值的情况
                if not self.left and not self.right:
                    ans.append(0)
                else:
                    ans.append((self.left_sum + len(self.left) * abs((-self.left[0]) - self.mid) +
                                self.right_sum + len(self.right) * abs(self.right[0] - self.mid)) % self._MOD)
            else:  # 当前有偶数个差值的情况
                ans.append((self.left_sum +
                            len(self.left) * abs(self.right[0] - (-self.left[0])) +
                            self.right_sum) % self._MOD)  # len(left) == len(right)

            # print("添加:", differ, ";", self.left, self.mid, self.right, ":",
            #       (self.left_sum, self.right_sum), "->", ans[-1])

        return ans

    def left_pop(self):
        """弹出中位数左侧的差值堆的最大值"""
        old_left = -heapq.heappop(self.left)
        if len(self.left) > 1:
            self.left_sum -= len(self.left) * abs((-self.left[0]) - old_left)
        else:
            self.left_sum = 0
        return old_left

    def left_push(self, differ):
        """向中位数左侧的差值堆插入值"""
        if len(self.left) == 0:
            heapq.heappush(self.left, -differ)
            self.left_sum = 0
        else:
            if differ <= (-self.left[0]):
                self.left_sum += abs(differ - (-self.left[0]))
                heapq.heappush(self.left, -differ)
            else:
                old_left = (-self.left[0])
                heapq.heappush(self.left, -differ)
                self.left_sum += (len(self.left) - 1) * abs((-self.left[0]) - old_left)

    def right_pop(self):
        """弹出中位数右侧的差值堆的最小值"""
        old_right = heapq.heappop(self.right)
        if len(self.right) > 1:
            self.right_sum -= len(self.right) * abs(self.right[0] - old_right)
        else:
            self.right_sum = 0
        return old_right

    def right_push(self, differ):
        """向中位数右侧的差值堆插入值"""
        if len(self.right) == 0:
            heapq.heappush(self.right, differ)
            self.right_sum = 0
        else:
            if differ >= self.right[0]:
                self.right_sum += abs(differ - self.right[0])
                heapq.heappush(self.right, differ)
            else:
                old_right = self.right[0]
                heapq.heappush(self.right, differ)
                self.right_sum += (len(self.right) - 1) * abs(self.right[0] - old_right)


if __name__ == "__main__":
    print(Solution().numsGame([3, 4, 5, 1, 6, 7]))  # [0,0,0,5,6,7]
    print(Solution().numsGame([1, 2, 3, 4, 5]))  # [0,0,0,0,0]
    print(Solution().numsGame([1, 1, 1, 2, 3, 4]))  # [0,1,2,3,3,3]
